#pragma once
void three_way_quick_sort(int arr[], int left, int right)
{
	int key = arr[left];
	int i = left;
	int l = left;
	int r = right;
	if (left >= right)
		return;
	while (i <= r)
	{
		if (arr[i] < key)
			swap(arr[i++], arr[l++]);
		else if (arr[i] > key)
			swap(arr[i], arr[r--]);
		else
			i++;
	}
	three_way_quick_sort(arr, left, l);
	three_way_quick_sort(arr, r + 1, right);
}